package com.atwulidun.graph.adjacentmatrix;

import java.util.*;

public class GraphDemo {
    public static void main(String[] args) {
        // 定义顶点的个数
        int n = 5;
        // 创建一张图
        Graph graph = new Graph(n);
        // 定义五个顶点
        String[] vertex = {"A", "B", "C", "D", "E"};
        // 往图中添加顶点
        for (String s : vertex) {
            graph.insertVertex(s);
        }
        // 添加边(A-B A-C B-C B-D B-E)
        graph.insertEdges(0, 1, 1);
        graph.insertEdges(0, 2, 1);
        graph.insertEdges(1, 2, 1);
        graph.insertEdges(1, 3, 1);
        graph.insertEdges(1, 4, 1);
        // 打印图
//        graph.show();
        // 深度优先遍历(递归(回溯))
        graph.dfs();
        // 深度优先遍历(非递归(栈))
//        graph.dfs1();
        // 广度优先遍历
//        graph.bfs();
    }
}

class Graph {
    // 保存顶点
    private ArrayList<String> vertexList;
    // 记录顶点是否被访问过
    private boolean[] isVisited;
    // 保存边
    private int[][] edges;
    // 保存边的数量
    private int numOfEdges;

    // 构造方法，传入顶点的个数，边的数量一开始默认为0
    public Graph(int n) {
        vertexList = new ArrayList<>(n);
        isVisited = new boolean[n];
        edges = new int[n][n];
    }

    // 插入顶点的方法
    public void insertVertex(String vertex) {
        vertexList.add(vertex);
    }

    // 添加边的方法
    public void insertEdges(int v1, int v2, int weight) {
        // 无向图是对称的
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        numOfEdges++;
    }

    // 获取顶点个数的方法
    public int getNumOfVertex() {
        return vertexList.size();
    }

    // 获取边数量的方法
    public int getNumOfEdges() {
        return numOfEdges;
    }

    // 根据下标获取顶点值的方法(0->A,1->B,2->C)
    public String getValueByIndex(int index) {
        return vertexList.get(index);
    }

    // 根据顶点下标获取权重的方法
    public int getWeight(int v1, int v2) {
        return edges[v1][v2];
    }

    // 打印图的方法
    public void show() {
        for (int[] edge : edges) {
            System.out.println(Arrays.toString(edge));
        }
    }

    // 获取下标为index的顶点第一个邻接顶点的方法
    //    A  B  C  D  E  F  G
    // A  0  1  1  1  1  0  1
    // 比如说获取A的第一个邻接顶点，那么此时index == 0，其第一个邻接顶点为B，下标为1
    // 如果当前顶点没有邻接顶点，那么返回-1
    public int getFirstNeighbor(int index) {
        for (int i = 0; i < edges.length; i++) {
            if (edges[index][i] > 0) {
                return i;
            }
        }
        return -1;
    }

    // 获取v1顶点的邻接顶点v2的下一个v1顶点的邻接顶点
    //    A  B  C  D  E  F  G
    // A  0  1  1  1  1  0  1
    // 比如说v1 == 0，v2 == 5，那么这里相当于获取A的邻接顶点E的下一个A的邻接顶点，即为G
    public int getNextNeighbor(int v1, int v2) {
        for (int i = v2 + 1; i < edges.length; i++) {
            if (edges[v1][i] > 0) {
                return i;
            }
        }
        return -1;
    }

    // 以下三个为深度优先遍历对应的方法
    // 一、图的深度优先遍历(递归方法(回溯算法))
    // 能进入该方法的顶点都是没有被访问过的
    // 相当于根据第一次的选择做出第二次的选择！！！！！！！！！！
    public void dfs(int i) {
        // 先把当前顶点的信息打印出来
        System.out.print(vertexList.get(i) + "->");
        // 把当前顶点设置为已经被访问
        isVisited[i] = true;
        // 以下就是对回溯算法进行第二次的选择，选择范围必须是跟顶点i相联通的其他顶点(w != -1就能体现这一点)，!isVisited[w]是剪枝操作！！！！！
        // 获取当前顶点的第一个邻接顶点
        int w = getFirstNeighbor(i);
        //    A  B  C  D  E  F  G
        // A  0  1  1  1  1  0  1
        // 当第一个邻接顶点连续存在时，进入while循环
        // 比如说A的第一个邻接顶点是B，B的第一个邻接顶点是C，一直连续存在到E，到了F时就要跳出while循环了
        // 在循环的过程中，B  C  D  E中的某一个顶点可能是被访问过的，也可能是没被访问过的，但是都不影响while循环的继续，只是没被访问过的才能进入下一层的递归而已！！！！！
        while (w != -1) {
            // 如果w顶点没有被访问过，那么可以以w为当前顶点进入下一层的递归；如果被访问过了就跳过
            if (!isVisited[w]) {
                dfs(w);
            }
            // 获取i顶点的下一个邻接顶点
            w = getNextNeighbor(i, w);
        }
//        for (int j = 0; j < edges.length; j++) {
//            if (edges[i][j] == 1 && !isVisited[j]) {
//                dfs(j);
//            }
//        }
    }
    /*
    注意：
     int w = getFirstNeighbor(i);
     while (w != -1) {
         if (!isVisited[w]) {
            dfs(w);
         }
         w = getNextNeighbor(i, w);
     }
     以上代码可以用下面的for循环来代替：
     for (int j = 0; j < edges.length; j++) {
         if (edges[i][j] == 1 && !isVisited[j]) {
             dfs(j);
         }
     }
     */


    // 二、对于非联通图的情况，还要再重载一个dfs方法
    //    A  B  C  D  E  F  G
    // A  0  1  1  1  1  0  1
    // 比如遍历到F的时候，被跳过了，此时又要从A的下一个结点B开始进行遍历，若B被访问过了，就从下一个C开始，依次类推
    // 相当于对每一个顶点都要做一次dfs
    public void dfs() {
        // 这里是回溯算法的第一次做选择，对于选择的范围就是任意一个顶点，没有其他的限制！！！！！！！
        for (int i = 0; i < vertexList.size(); i++) {
            if (!isVisited[i]) {
                dfs(i);
            }
        }
    }

    // 三、图的深度优先遍历(非递归方法，利用栈来实现)
    // 相当于根据第一次的选择i做出第二次的选择！！！！！！
    public void dfs1(int i) {
        // 先把当前顶点信息打印出来
        System.out.print(vertexList.get(i) + "->");
        // 把当前顶点设置为已经被访问
        isVisited[i] = true;
        // 定义一个栈
        Deque<Integer> stack = new LinkedList<>();
        // 将当前顶点push进栈
        stack.push(i);
        // 定义一个表示栈顶元素变量
        int top;
        // 定义一个表示栈顶元素邻接顶点的变量
        int w;
        // 将i入栈是为了能进入下面的循环
        while (!stack.isEmpty()) {
            // 获取栈顶元素
            top = stack.pop();
            // 获取栈顶元素的邻接顶点
            w = getFirstNeighbor(top);
            while (w != -1) {
                if (!isVisited[w]) {
                    System.out.print(vertexList.get(w) + "->");
                    isVisited[w] = true;
                    stack.push(w);
                }
                w = getNextNeighbor(top, w);
            }
            // 其实，在while循环里，只要找到第一个与top相联通但是又没被访问过的顶点，直接break即可
            // 因为深度优先遍历只关心top的某一个与其相联通但是又没被访问过的顶点，然后又以该顶点为当前顶点找下一个与其相联通但是又没被访问过的结点
            //    A  B  C  D  E  F  G
            // A  0  1  1  1  1  0  1
            // 比如说选择了B，那么通过B已经将C D E 给遍历了；再选择C，由于C D E 都被遍历了，所以被!isVisited[w]给剪枝掉了
//            while (w != -1) {
//                if (!isVisited[w]) {
//                    System.out.print(vertexList.get(w) + "->");
//                    isVisited[w] = true;
//                    stack.push(w);
//                    break;
//                }
//                w = getNextNeighbor(top, w);
//            }
        }
    }

    // 四、对于非联通图的情况，还要对dfs1(int i)进行一个重载
    public void dfs1() {
        for (int i = 0; i < vertexList.size(); i++) {
            if (!isVisited[i]) {
                dfs1(i);
            }
        }
    }

    // 以下两个为广度优先遍历对应的方法
    // 一、图的广度优先遍历
    public void bfs(int i) {
        // 先把当前顶点的信息打印出来
        System.out.print(vertexList.get(i) + "->");
        // 把当前顶点设置为已被访问
        isVisited[i] = true;
        // 定义一个队列，将已被访问过的顶点加入到队列中
        // 这里用链表实现队列，因为有addAtLast()和removeFirst()方法
        LinkedList<Integer> queue = new LinkedList<>();
        // 将当前顶点加入到队列
        queue.addLast(i);
        // 定义一个获取队列首顶点的变量
        int u;
        // 定义一个获取队列首顶点的第一个邻接顶点的变量
        int w;
        // 下面用while循环将队列里的顶点依次取出
        // 把i放入到队列中是为了能进入下面的循环！！！！！！！
        while (!queue.isEmpty()) {
            u = queue.removeFirst();
            w = getFirstNeighbor(u);
            // 开始对u进行横向遍历
            while (w != -1) {
                if (!isVisited[w]) {
                    // 注意：广度优先遍历不用递归!!!!!!!!!!!!
                    // 先把当前顶点的信息打印出来
                    System.out.print(vertexList.get(w) + "->");
                    // 把当前顶点设置为已被访问
                    isVisited[w] = true;
                    // 将当前顶点加入到队列
                    queue.addLast(w);
                }
                // 横向遍历u的下一个顶点
                // 特别注意：这里的u特别容易写成i，必须要以u为前驱结点！！！！！！！！！！！！！！！！！！！！
                w = getNextNeighbor(u, w);
            }
        }
    }

    // 二、若图为非联通图，则需要对每个顶点依次进行广度优先遍历
    public void bfs() {
        for (int i = 0; i < vertexList.size(); i++) {
            if (!isVisited[i]) {
                bfs(i);
            }
        }
    }
}

